package HomeWork;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 姚东名
 * Date: 2024-05-12
 * Time: 21:30
 */
public class Test0512 {
    public static int majorityElement(int[] array) {
        //对数组进行排序，在中间的一定是最多的数（多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素）
        Arrays.sort(array);
        return array[array.length / 2];
    }
    public static void main(String[] args) {
        //3.给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
        //你可以假设数组是非空的，并且给定的数组总是存在多数元素。
        //输入：[3,2,3] -> 输出：3
        int[] array = { 3,2,3 };
        System.out.println(majorityElement(array));//3
    }
    public static int[] twoSum1(int[] array, int target) {
        int[] ret = { -1,-1 };
        for (int i = 0; i < array.length - 1; i++) {
            for(int j = array.length - 1; j > i; j--) {
                if(array[i] + array[j] == target) {
                    ret[0] = i;
                    ret[1] = j;
                }
            }
        }
        return ret;
    }
    public static void main12(String[] args) {
        //2.给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
        //你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
        //你可以按任意顺序返回答案。
        //输入：nums = [2,7,11,15], target = 9 -> 输出：[0,1]
        //解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
        int[] nums = {2,7,11,15};
        int target = 9;
        int[] ret = twoSum1(nums, target);
        System.out.println(Arrays.toString(ret));
    }
    public static void main11(String[] args) {
        //调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序。
        //[1,2,3,4,5,6] -> [1, 5, 3, 4, 2, 6]
        int[] array = { 1,2,3,4,5,6 };
        int left = 0;
        int right = array.length - 1;
        while(left < right) {
            if(left < right && array[left] % 2 == 1) {
                left++;
            }
            if(left < right && array[right] % 2 == 0) {
                right--;
            }
            int tmp = array[left];
            array[left] = array[right];
            array[right] = tmp;
        }
        System.out.println(Arrays.toString(array));
    }
    public static int[] twoSum(int[] numbers, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            int complement = target - numbers[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement), i};
            }
            map.put(numbers[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    public static void main10(String[] args) {
        int[] numbers = {2, 7, 11, 15};
        int target = 9;
        try {
            int[] result = twoSum(numbers, target);
            System.out.println("The two indices are: " + Arrays.toString(result));
        } catch (IllegalArgumentException e) {
            System.out.println(e.getMessage());
        }
    }
    public static boolean consOddNum(int[] array) {
        //数组不能为空：
        if(array == null || array.length < 3) {
            return false;
        }
        for (int i = 0; i <= array.length - 3; i++) {
            if(array[i] % 2 == 1 && array[i + 1] % 2 == 1 && array[i + 2] % 2 == 1) {
                return true;
            }
        }
        return false;
    }
    public static void main9(String[] args) {
        //给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false
        //不存在连续三个元素都是奇数的情况。
        //存在连续三个元素都是奇数的情况
        int[] array = {1, 4, 5, 7, 9};
        boolean odd = consOddNum(array);
        if(odd) {
            System.out.println("存在连续三个元素都是奇数的情况");
        }else {
            System.out.println("不存在连续三个元素都是奇数的情况");
        }
    }

    public static Integer findMajorityElement(int[] nums) {
        Integer candidate = null;
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        // 验证candidate是否为多数元素
        count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }

        if (count > nums.length / 2) {
            return candidate;
        } else {
            return null; // 如果没有多数元素则返回null
        }
    }

    public static void main8(String[] args) {
        //给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
        //你可以假设数组是非空的，并且给定的数组总是存在多数元素。
        int[] arr1 = {3, 3, 4, 2, 2, 2, 5, 2, 2}; // 示例数组
        System.out.println("多数元素是: " + findMajorityElement(arr1));
    }

    public static void main7(String[] args) {
        //给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
        //[4,1,2,1,2] -> 4
        int[] array = {4, 1, 2, 1, 2};
        int ret = array[0];
        if (array.length > 1) {
            for (int i = 1; i < array.length; i++) {
                ret ^= array[i];
            }
        }
        System.out.println(ret);
    }


    public static void arraySort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] >= array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
    }

    public static void main5(String[] args) {
        //给定一个整型数组, 实现冒泡排序(升序排序)
        int[] array = {2, 9, 6, 3, 4, 5, 1};
        arraySort(array);
        System.out.println(Arrays.toString(array));
    }

    public static void main4(String[] args) {
        //3.给定一个有序整型数组, 实现二分查找
        int[] array = {1, 2, 3, 4, 5, 6};
        //利用库方法：
        int ret = Arrays.binarySearch(array, 3);
        System.out.println("下标为：" + ret);
    }

    public static void main3(String[] args) {
        //2.奇数位于偶数之前
        //调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序。
        //如数组：[1,2,3,4,5,6]
        //调整后可能是：[1, 5, 3, 4, 2, 6]
        //创建一个新的数组：
        int[] originalArray = {1, 2, 3, 4, 5, 6};
        int[] separatedArray = new int[originalArray.length];
        int oddIndex = 0; // 奇数放置的索引
        int evenIndex = originalArray.length - 1; // 偶数放置的索引，从后往前放

        // 遍历原数组
        for (int num : originalArray) {
            if (num % 2 != 0) { // 如果是奇数
                separatedArray[oddIndex++] = num; // 放在前面
            } else { // 如果是偶数
                separatedArray[evenIndex--] = num; // 放在后面
            }
        }
        System.out.println(Arrays.toString(separatedArray));
    }

    public static void main2(String[] args) {
        //2.奇数位于偶数之前
        //调整数组顺序使得奇数位于偶数之前。调整之后，不关心大小顺序。
        //如数组：[1,2,3,4,5,6]
        //调整后可能是：[1, 5, 3, 4, 2, 6]
        //创建一个新的数组：
        int[] array = {1, 2, 3, 4, 5, 6};
        int[] array1 = new int[array.length];
        int left = 0;
        int right = array.length - 1;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 != 0) {
                array[left++] = array1[i];
            } else {
                array[right--] = array1[i];
            }
        }
        System.out.println(Arrays.toString(array1));
    }

    public static int[] transform(int[] array) {
        for (int i = 0; i < array.length; i++) {
            array[i] = array[i] * 2;
        }
        return array;
    }

    public static void main1(String[] args) {
        //1.改变原有数组元素的值
        //实现一个方法 transform, 以数组为参数, 循环将数组中的每个元素 乘以 2 , 并设置到对应的数组元素上. 例如 原数组为 {1, 2, 3}, 修改之后为 {2, 4, 6}
        int[] array = {1, 2, 3};
        System.out.println("原数组为: " + Arrays.toString(array));
        transform(array);
        System.out.println("修改之后: " + Arrays.toString(array));

    }
}
